package treeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution9 {

    List<List<Integer>> ret = new LinkedList<List<Integer>>();  //结果
    LinkedList<Integer> path = new LinkedList<Integer>();  //记录遍历的路径
    //计算所有路径的总和
    public List<List<Integer>> pathSum(TreeNode root, int sum) {

       dfs(root,sum);

        return ret;

    }

    //Depth First Search 深度优先搜索  达到被搜索结构的叶结点 ，如果还没有结果path返回上一步
    public void dfs(TreeNode root,int sum){
        if(root==null){
            return ;
        }
        sum = sum -root.val;
        path.offerLast(root.val);  //
        if(root.left==null&&root.right==null&&sum==0){
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left,sum);
        dfs(root.right,sum);

        path.pollLast();

    }

    public static void main(String[] args) {
        TreeNode root = TreeNodeUtils.getTestTreeNode();
        System.out.println(new Solution9().pathSum(root,11));
    }

}
